package com.guqj.basis.datastruct.singlelist;

import java.util.NoSuchElementException;

/**
 * 单向链表
 * 
 * @author guqj
 * @date 2017年3月22日
 */
public class LinkList {

	private Node head; // 头节点
	private Node tail; // 尾节点
	private int size; // 当前节点数

	public LinkList() {

	}

	public void add(Object data) {
		final Node l = tail;
		final Node newNode = new Node(data);
		tail = newNode;
		if (l == null) {
			head = newNode;
		} else {
			l.next = newNode;
		}
		size++;
	}

	public void addFirst(Object data) {
		final Node newNode = new Node(data);
		final Node x = head;
		head = newNode;
		if (x == null) {
			tail = newNode;
		} else {
			head.next = x;
		}
		size++;
	}

	public boolean remove(Object o) {
		if (o != null) {
			Node current = head;
			Node prev = head;
			for (Node x = head; x != null; x = x.next) {
				if (o.equals(x.obj)) {
					break;
				}
				prev = current;
				current = current.next;
			}
			if (current == head) {
				head = current.next;
			} else {
				prev.next = current.next;
			}
			size--;
			return true;
		}
		return false;
	}

	public Object get(int index) {
		if (!checkPosition(index)) {
			throw new IndexOutOfBoundsException();
		}
		Node x = head;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x.obj;
	}

	public Object getFirst() {
		final Node x = head;
		if (x == null) {
			throw new NoSuchElementException();
		}
		return x.obj;
	}

	public Object getLast() {
		final Node x = tail;
		if (x == null) {
			throw new NoSuchElementException();
		}
		return x.obj;
	}

	public void add(int index, Object obj) {
		if (!checkPosition(index)) {
			throw new IndexOutOfBoundsException();
		}
		if (index == 0) {
			addFirst(obj);
		} else if (index == size) {
			add(obj);
		} else {
			Node current = head;
			Node prev = head;
			int s = 0;
			for (Node x = head; x != null; x = x.next) {
				if (s >= index) {
					break;
				}
				prev = current;
				current = current.next;
				s++;
			}
			final Node newNode = new Node(obj);
			prev.next = newNode;
			newNode.next = current;
			size++;
		}
	}

	private boolean checkPosition(int index) {
		return index >= 0 && index < size;
	}

	public int size() {
		return size;
	}

	public static void main(String[] args) {
		LinkList list = new LinkList();
		list.add("Java");
		list.add("Python");
		list.add("GO");
		list.remove("Java");
		list.add(1, "PHP");
		list.add(1, "JavaScript");
		int size = list.size();
		for (int i = 0; i < size; i++) {
			System.out.print(list.get(i) + " ");
		}
	}
}
